#include <bits/stdc++.h>
using namespace std;
const int N = 1e6;
class Solution
{
  public:
    int dfs(int x, vector<int> &nums)
    {
        int res = 0;
        if (x >= nums.size())
            return 0;
        res = max(dfs(x + 1, nums), dfs(x + 2, nums) + nums[x]);
        return res;
    }
    int dp[N];
    int rob(vector<int> &nums)
    {
        // int ans = dfs(0, nums);
        // return ans;
        int n = nums.size();
        for (int i = n - 1; i >= 0; i--)
        {
            dp[i] = max(dp[i + 1], dp[i + 2] + nums[i]);
        }
        return dp[0];
    }
};